package com.heima.DP.bagMore;

import java.util.Scanner;

/*
*有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
每件物品有无数个，求解将哪些物品装入背包里物品价值总和最大。
例如：
物品  重量  价值
物品0  1   15
物品1  3   20
物品2  4   30
*/

/*
 * @description 这与一维的01背包在形式上只有一个差异：遍历背包是从前往后遍历的。记住这个代码都行。
 * 但是真正的原理在于，你从前面遍历就保证了可以一件物品可以重复取值直至达到承重量
 * @params
 * @return
 */

public class bagMore {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //int M = input.nextInt();
        int M = 3;
        //int bagWeight = input.nextInt();
        int bagWeight = 4;
        int[] weight = new int[M];
        int[] value = new int[M];

        //for (int i = 0; i < M; i++) {
        //    weight[i]=input.nextInt();
        //}
        //for (int i = 0; i < M; i++) {
        //     value[i]=input.nextInt();
        //}

        weight = new int[]{1, 3, 4};
        value = new int[]{15, 20, 30};
        System.out.println(solveOneParam(M, bagWeight, weight, value));
    }

    /*
     * @description 牛逼，一维数组区区6行代码！就可以解决完全dp,和01背包的仅仅遍历顺序不同。
        在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！因为这里
     * @params
     * @return
     */

    private static int solveOneParam(int m, int bagWeight, int[] weight, int[] value) {
        //dp[j]定义为容量为j的背包最多能装下的物品价值！！！！！！！！！！！！！！！！！！！！！！！

        int[] dp = new int[bagWeight + 1];
        dp[0] = 0;
        //遍历物品
        for (int i = 0; i < m; i++) {
            for (int j = weight[i]; j <=bagWeight; j++) {//注意一定要相等！！！注意这里是正序了！！j--
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                System.out.print("dp[" + j + "]=" + dp[j] + "\t");
            }
            System.out.println();
        }
        return dp[bagWeight];
    }
}